显然
令
令
推导的部分就结束了。
将换一种写法:
其中 为 出现的次数。可以发现:
再令
对比系数发现:
另外一个 是一个积性函数,可以线筛。
#include <cstdio>
#define Mod 998244353
const int MAXN = 1e7;
int n , k , cnt , prime[ MAXN + 5 ] , f[ MAXN + 5 ] , s[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
int Quick_pow( int x , int po ) {
int Ans = 1;
for( ; po ; po >>= 1 , x = 1ll * x * x % Mod )
if( po & 1 ) Ans = 1ll * Ans * x % Mod;
return Ans;
}
void sieve( ) {
f[ 1 ] = s[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ cnt ] = i;
s[ i ] = Quick_pow( i , k );
f[ i ] = i - 1;
}
for( int j = 1 ; j <= cnt && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
s[ i * prime[ j ] ] = 1ll * s[ i ] * s[ prime[ j ] ] % Mod;
if( i % prime[ j ] == 0 ) {
if( i / prime[ j ] % prime[ j ] != 0 )
f[ i * prime[ j ] ] = ( 1ll * -prime[ j ] * f[ i / prime[ j ] ] % Mod + Mod ) % Mod;
break;
}
f[ i * prime[ j ] ] = 1ll * f[ i ] * f[ prime[ j ] ] % Mod;
}
}
for( int i = 2 ; i <= MAXN ; i ++ ) {
f[ i ] = ( 1ll * f[ i ] * s[ i ] % Mod + f[ i - 1 ] ) % Mod;
s[ i ] = ( s[ i ] + s[ i - 1 ] ) % Mod;
}
for( int i = 2 ; i <= MAXN ; i ++ )
s[ i ] = ( s[ i ] + s[ i - 1 ] ) % Mod;
}
int Sum( int n ) {
return ( ( s[ 2 * n ] - 2ll * s[ n ] ) % Mod + Mod ) % Mod;
}
int Solve( int n ) {
int Ans = 0;
for( int l = 1 , r ; l <= n ; l = r + 1 ) {
r = n / ( n / l );
Ans = ( Ans + 1ll * ( f[ r ] - f[ l - 1 ] + Mod ) % Mod * Sum( n / l ) % Mod ) % Mod;
}
return Ans;
}
int main( ) {
long long t;
scanf("%d %lld",&n,&t); k = t % ( Mod - 1 );
sieve( );
printf("%d\n", Solve( n ) );
return 0;
}